package linkedList.递归;

import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 回文链表234.java
 * @Description TODO  https://leetcode-cn.com/problems/palindrome-linked-list/
 * @createTime 2021年03月09日 13:45:00
 */
public class 回文链表234 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(2);
        ListNode listNode4 = new ListNode(1);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
       // listNode3.next = listNode4;
        //listNode4.next = listNode5;
        回文链表234 ii92 = new 回文链表234();
        boolean palindrome = ii92.isPalindrome(listNode1);
        System.out.println(palindrome);
    }
    /**
     * 请判断一个链表是否为回文链表
     * <p>
     * todo：寻找回文串的核心思想是从中心向两端扩展，因为回文串长度可能为奇数也可能是偶数，长度为奇数时只存在一个中心点，而长度为偶数时存在两个中心点，所以上面这个函数需要传入l和r
     * todo：寻找链表的中心点可以用快慢双指针的方式来寻找。https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/shou-ba-shou-shua-lian-biao-ti-mu-xun-lian-di-gui-si-wei/pan-duan-hui-wen-lian-biao
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }
        //寻找中心点
        ListNode slow = head, fast = head,temp=null;
        //两个指针同时往后移动，如果fast指针没有指向null，说明是奇数个，如果fast为null，说明是偶数个
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //此时的slow为中间点,如果是偶数个则分割点就是slow，如果是奇数个分割点是slow的next
        if (fast==null){
            temp=slow;
        }else {
            temp= slow.next;
        }
        ListNode listNode = reverseNode(temp);
        ListNode p1 = head, p2 = listNode;
        boolean result = true;
        while (p2 != null) {
            if (p2.val!=p1.val){
                 result=false;
            }
            p1=p1.next;
            p2=p2.next;
        }
        return result;
    }

    private ListNode reverseNode(ListNode pre) {
        if (pre == null) {
            return pre;
        }
        if (pre.next == null) {
            return pre;
        }
        ListNode node = reverseNode(pre.next);
        pre.next.next = pre;
        pre.next = null;
        return node;
    }
}
